package algorithm.swordoff;


/**
 * 0~n-1中缺失的数字
 *
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 * 二分法,注意上下界的迭代规则
 */

public class SQ53_2 {

    public int missingNumber(int[] nums) {
        return findMissingNumber(nums, 0, nums.length);
    }

    private int findMissingNumber(int[] nums, int begin, int end) {
        while (begin < end) {
            int mid = begin + (end-begin)/2;
            if (nums[mid] != mid) end = mid;
            else begin = mid+1;
        }
        return begin;
    }

    public static void main(String[] args) {
        SQ53_2 sq53_2 = new SQ53_2();
        int[] ints = {1,2,3};
        System.out.println(sq53_2.missingNumber(ints));
    }
}
